use std::{cell::RefCell, rc::Rc};

type Link<T> = Option<Rc<RefCell<Node<T>>>>;

#[derive(Debug)]
pub struct Node<T> {
    pub value: T,
    pub next: Link<T>,
    pub prev: Link<T>,
}

#[derive(Debug)]
pub struct LinkedList<T> {
    pub head: Link<T>,
    pub tail: Link<T>,
}

impl<T> Node<T> {
    pub fn new(value: T) -> Self {
        Node {
            value,
            next: None,
            prev: None,
        }
    }
}

impl<T> LinkedList<T> {
    pub fn new() -> Self {
        LinkedList {
            head: None,
            tail: None,
        }
    }

    pub fn push_front(&mut self, value: T) {
        let node = Rc::new(RefCell::new(Node::new(value)));
        match self.head.take() {
            None => {
                self.head = Some(Rc::clone(&node));
                self.tail = Some(node);
            }
            Some(ref data) => {
                self.head = Some(Rc::clone(&node));
                node.borrow_mut().next = Some(Rc::clone(data));
                data.borrow_mut().prev = Some(node);
            }
        };
    }

    pub fn push_back(&mut self, value: T) {
        let node = Rc::new(RefCell::new(Node::new(value)));
        match self.tail.take() {
            None => {
                self.tail = Some(Rc::clone(&node));
                self.head = Some(node);
            }
            Some(data) => {
                self.tail = Some(Rc::clone(&node));
                node.borrow_mut().prev = Some(Rc::clone(&data));
                data.borrow_mut().next = Some(node);
            }
        }
    }

    pub fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            match node.borrow_mut().next.as_ref() {
                None => {
                    self.tail = None;
                    self.head = None;
                }
                Some(data) => {
                    self.head = Some(Rc::clone(data));
                    data.borrow_mut().prev = None;
                }
            };
            // if let Some(new_head) = node.borrow_mut().next.take() {
            //     new_head.borrow_mut().prev = None;
            //     self.head = Some(new_head);
            // } else {
            //     self.tail.take();
            // }
            Rc::try_unwrap(node).ok().unwrap().into_inner().value
        })
    }

    pub fn pop_back(&mut self) -> Option<T> {
        self.tail.take().map(|node| {
            match node.borrow().prev.as_ref() {
                None => {
                    self.head = None;
                    self.tail = None;
                }
                Some(prev) => {
                    prev.borrow_mut().next = None;
                    //node.borrow_mut().prev = None;
                    self.tail = Some(Rc::clone(prev));
                }
            }
            Rc::try_unwrap(node).ok().unwrap().into_inner().value
        })
    }
}

#[cfg(test)]
mod test {

    use super::*;

    #[test]
    fn test() {
        let mut list = LinkedList::new();
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        assert_eq!(list.pop_back(), Some(3));
        assert_eq!(list.pop_back(), Some(2));
        assert_eq!(list.pop_back(), Some(1));
        assert_eq!(list.pop_back(), None);

        let mut list = LinkedList::new();
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);
        assert_eq!(list.pop_front(), Some(3));
        assert_eq!(list.pop_front(), Some(2));
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), None);

        let mut list = LinkedList::new();
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), Some(2));
        assert_eq!(list.pop_front(), Some(3));
        assert_eq!(list.pop_front(), None);

        let mut list = LinkedList::new();
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);
        assert_eq!(list.pop_back(), Some(1));
        assert_eq!(list.pop_back(), Some(2));
        assert_eq!(list.pop_back(), Some(3));
        assert_eq!(list.pop_back(), None);
    }
}
